package dp;

import java.util.Arrays;

/**
 * 最后一块石头的重量
 */
public class WeightOfLastStone {

    public static void main(String[] args) {
        int[] stones = new int[] {2,7,4,1,8,1};
        int sum = Arrays.stream(stones)
                .reduce(Integer::sum)
                .orElse(0);
        int target = sum / 2;
        // a+b=s b=s-a  |a-b|=|2a-s|
        int result = getWeightOfLastStone(stones, target);
        System.out.println(Math.abs(2*result-sum));
    }

    private static int getWeightOfLastStone(int[] stones,int target) {
        // dp数组表示容量为j的背包所背的最大价值
        int[] dp = new int[target + 1];

        for (int i = 0; i < stones.length; i++) {
            for (int j = target;j>=stones[i];j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i]] + stones[i]);
            }
        }
        Common.print1dArr(dp);
        return dp[target];
    }
}
